package 排序;

//快速排序
public class quicksort {
    public static void main(String[] args) {
        int[] arr = {6, 3, 4, 5, 1, 2, 9, 7, 8};
        int[] quicktext = quicktext(arr, 0, arr.length - 1);
        //输出数组
        for (int i = 0; i < quicktext.length; i++) {
            System.out.print(quicktext[i] + " ");
        }
    }

    //形参为：要排序的数组，开始索引，结束索引
    private static int[] quicktext(int[] arr, int i, int j) {
        //定义开始索引和结束索引
        int start = i;
        int end = j;
        //递归停止的条件
        if (start > end){
            return arr;
        }
        //定义基准数,即0索引数
        int base = arr[i];
        //排序停止条件
        while (start != end) {
            //顺序必须从end到start

            //从end开始往前找比基准数小的数
            while (true) {
                if (arr[end] < base || start >= end) {
                    break;
                }
                end--;
            }

            //从start开始往后找比基准数大的数
            while (true) {
                if (arr[start] > base || start >= end) {
                    break;
                }
                start++;
            }
            //将start和end索引的数进行交换
            int t = arr[start];
            arr[start] = arr[end];
            arr[end] = t;
        }
        //将这个数组的开始索引i和end或start索引的数进行交换,因为base已经找到所处的位置
        int t1 = arr[i];
        arr[i] = arr[end];
        arr[end] = t1;

        //让base的左边进行排序
        quicktext(arr,i,start-1);
        //让base的右边进行排序
        quicktext(arr,start+1,j);

        return arr;
    }
}
